#include <stdlib.h>
#include <string.h>

#include "myDataStruct.h"
#include "simdef.h"


/*-------------------------- queue --------------------------*/
inline int32_t isQueEmpty(Queue Q)
{
    return Q->size == 0;
}

inline int32_t isQueFull(Queue Q)
{
    return Q->size == Q->capacity;
}

Queue createQueue(uint32_t NElements)
{
    Queue Q;
    Q = (Queue)malloc(sizeof(struct QueueRecord));
    if (Q == NULL)
        return NULL;
    Q->array = (QueueElem*)malloc(sizeof(QueueElem) * NElements);
    if (Q->array == NULL)
    {
        return NULL;
    }
    Q->capacity = NElements;
    emptyQue(Q);

    return Q;
}

void emptyQue(Queue Q)
{
    Q->size = 0;
    Q->front = 1;
    Q->rear = 0;
}

void disposeQue(Queue Q)
{
    if (Q != NULL)
    {
        free(Q->array);
        free(Q);
    }
}

static uint32_t succ(uint32_t value, Queue Q)
{
    if (++value == Q->capacity)
        value = 0;
    return value;
}

int32_t inQue(QueueElem data, Queue Q)
{
    if (isQueFull(Q))
        return -1;
    else
    {
        Q->size++;
        Q->rear = succ(Q->rear, Q);
        Q->array[Q->rear] = data;
    }
    return 0;
}

int32_t deQue(QueueElem* data,Queue Q)
{

    if (isQueEmpty(Q))
        return -1;
    Q->size--;
    *data = Q->array[Q->front];
    Q->front = succ(Q->front, Q);
    return 0;
}

/*----------------------- Linked List -----------------------*/
List emptyList(List L)
{
    if (L != NULL)
        deleList(L);
    L = (List)malloc(sizeof(struct Node));
    if (L == NULL)
        return NULL;
    L->next = NULL;
    return L;
}

void deleList(List L)
{
    ListPos P, Tmp;

    P = L;
    while (P != NULL)
    {
        Tmp = P->next;
        free(P);
        P = Tmp;
    }
}

inline int32_t isListEmpty(List L)
{
    return L->next == NULL;
}

void deleNode(ListPos preNode)
{
    ListPos tmp= preNode->next;
    
    preNode->next = tmp->next;
    free(tmp);
}

int32_t insertNode(ListPos prenode, ListElem data)
{
    ListPos newNode;

    newNode = (ListPos)malloc(sizeof(struct Node));
    if (newNode == NULL)
        return -1;
    newNode->element = data;
    newNode->next = prenode->next;
    prenode->next = newNode;
    return 0;
}

int32_t appendNode(List L, ListElem data)
{
    ListPos p0=L;
    
    while (p0->next != NULL)
        p0= p0->next;
    return(insertNode(p0, data));
}

void printList(List L, void (*printMethod)(void *arg))
{
    int ii=0;
    ListPos pL=L;
    while(pL->next)
    {
        pL=pL->next;
        printf("node%02d: ",ii++);
        printMethod(&(pL->element));
        printf("\n");
    }
}

/* printMethod demo
void printInt(void* arg)
{
    printf("%d",*(int *)arg);
}
*/
/*----------------- jamp list -----------------*/
// https://djqueue.blog.csdn.net/article/details/105476382?
// spm=1001.2101.3001.6661.1&utm_medium=distribute.
// pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.
// pc_relevant_default&depth_1-utm_source=distribute.pc_relevant_t0.
// none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.
// pc_relevant_default&utm_relevant_index=1
SlList_t* createSlList()
{
    SlList_t *pSl=(SlList_t*)malloc(sizeof(SlList_t));
    if(!pSl) return NULL;
    SlNode_t *pHead=createSlNode(SKIPLIST_MAXLEVEL,0,NULL);
    if(!pHead)
    {
        free(pSl);
        return NULL;
    }
    for(int ii=0;ii<SKIPLIST_MAXLEVEL;ii++)
    {
        pHead->level[ii].forward=NULL;
        pHead->level[ii].span=0;
    }
    pHead->backward=NULL;
    pSl->head=pHead;
    pSl->tail=NULL;
    pSl->length=0;
    pSl->level=1;

    return pSl;
}

SlNode_t* createSlNode(int32_t level,
                    ScoreType score,
                    skiplistElem* element)
{
    SlNode_t *pNode=(SlNode_t*)malloc(sizeof(SlNode_t)
                        +level*sizeof(struct SkiplistLevel));
    if(pNode==NULL) return NULL;
    if(element!=NULL)
        pNode->element=*element;
    pNode->score=score;
    for(int ii=0;ii<level;ii++)
    {
        pNode->level[ii].forward=NULL;
        pNode->level[ii].span=0;
    }
    
    return pNode;
}

SlNode_t* insertNodeSl(SlList_t* slList,
                ScoreType score,
                skiplistElem* element)
{
    int32_t ii;
    int32_t level;
    SlNode_t *update[SKIPLIST_MAXLEVEL]; // 记录寻找元素过程中，每层能到达的最右节点
    SlNode_t *x=slList->head;
    uint32_t rank[SKIPLIST_MAXLEVEL]; // 记录寻找元素过程中，每层所跨越的节点数
    
    // printf("--------insert %2d --------\n",score);
    for(ii=slList->level-1;ii>=0;ii--)
    {
        rank[ii]=ii==(slList->level-1)?0:rank[ii+1];
        while(x->level[ii].forward &&
            x->level[ii].forward->score < score)
        {
            rank[ii]+=x->level[ii].span;
            x=x->level[ii].forward;
        }
        update[ii]=x;
    }

    // printf("  rank list:\n");
    // for(int jj=slList->level-1;jj>=0;jj--)
    //     printf("    rank[%2d] %2d\n",jj,rank[jj]);

    // printf("  update list:\n");
    // for(int jj=slList->level-1;jj>=0;jj--)
    //     if(update[jj]==slList->head)
    //         printf("    update[%2d] = head\n",jj);
    //     else if(update[jj]==NULL)
    //         printf("    update[%2d] = NULL\n",jj);
    //     else
    //         printf("    update[%2d] = %d\n",jj,update[jj]->score);

    level=slRandomLevel(); // 计算新的随机层数
    // 如果 level 比当前 skiplist 的最大层数还要大
    // 那么更新 slList->level 参数
    // 并且初始化 update 和 rank 参数在相应的层的数据
    if(level > slList->level)
    {
        for(ii=slList->level;ii<level;ii++)
        {
            rank[ii]=0;
            update[ii]=slList->head;
            update[ii]->level[ii].span=slList->length;
        }
        slList->level=level;
    }
    // 创建新节点
    x=createSlNode(level,score,element);
    // 根据update、rank两个数组，初始化新节点并设置相应的指针
    for(ii=0;ii<level;ii++)
    {
        x->level[ii].forward=update[ii]->level[ii].forward;
        update[ii]->level[ii].forward=x;
        x->level[ii].span=update[ii]->level[ii].span-(rank[0]-rank[ii]);
        update[ii]->level[ii].span=(rank[0]-rank[ii])+1;
    }
    // printf("  about x:\n");
    // printf("    x.score= %d\n",x->score);
    // for(int jj=0;jj<level;jj++)
    // {
    //     printf("    x[%2d].span=%2d\n",jj,x->level[jj].span);
    //     if(x->level[jj].forward==NULL)
    //         printf("    x[%2d] -> NULL\n",jj);
    //     else
    //         printf("    x[%2d] -> %d\n",jj,x->level[0].forward->score);
    // }
    // for(int jj=0;jj<level;jj++)
    //     printf("    update[%2d] -> %d\n",jj,update[jj]->level[jj].forward->score);

    // 更新沿途访问节点的span值
    for(ii=level;ii<slList->level;ii++)
    {
        update[ii]->level[ii].span++;
    }
    // 设置后退指针
    x->backward=(update[0]==slList->head)?NULL:update[0];
    if(x->level[0].forward)
        x->level[0].forward->backward=x;
    else
        slList->tail=x;
    
    slList->length++;
    
    return x;
}

uint32_t slRandomLevel()
{
    int32_t level=1;
    while(myRand()%0xff<(0xff>>SKIPLIST_P))
        level++;
    return level<SKIPLIST_MAXLEVEL?level:SKIPLIST_MAXLEVEL;
}

void deletNodeSl(SlList_t* slList,SlNode_t *node)
{
    int32_t levelII;
    SlNode_t *pre;

    pre=node->backward==NULL?slList->head:node->backward;
    // 更新下一节点的backward
    if(node->level[0].forward)
        node->level[0].forward->backward=pre;
    
    // 更新上一个节点
    pre->level[0].forward=node->level[0].forward;
    pre->level[0].span+=node->level[0].span-1;
    for(levelII=1;levelII<slList->level;levelII++)
    {
        pre=slList->head;
        while(pre->level[levelII].forward)
        {
            if(pre->level[levelII].forward==node)
            {
                pre->level[levelII].forward=node->level[levelII].forward;
                pre->level[levelII].span+=node->level[levelII].span-1;
                break;
            }
            if(pre->level[levelII].forward->score > node->score)
            {
                pre->level[levelII].span--;
                break;
            }
            pre=pre->level[levelII].forward;
        }
    }
    pre=node->backward==NULL?slList->head:node->backward;
    // 更新跳表tail level length
    if(slList->tail==node)
        if(pre==slList->head)
            slList->tail=NULL;
        else
            slList->tail=pre;
    for(levelII=slList->level-1;levelII>=0;levelII--)
        if(slList->head->level[levelII].forward!=NULL)
        {
            slList->level=levelII+1;
            break;
        }
    slList->length--;

    freeSlNode(node);
}

SlNode_t* serchSl(SlList_t* slList,ScoreType score,int32_t flag)
{
    int32_t levelII;
    SlNode_t* node=slList->head;
    SlNode_t* next;
    for(levelII=slList->level-1;levelII>=0;levelII--)
    {
        //printf("level %d\n",levelII);
        next=node->level[levelII].forward;
        if(next==NULL || next->score > score)
            continue;
        if(next->score == score)
            return next;
        else if(next->score < score)
        {
            node=next;
            levelII++;
        }
    }
    switch(flag){
        case 0: // equal
            return NULL;
        case 1: // greater than or equal
            return next;
        case 2: // less than or equal
            return node==slList->head?NULL:node;
        default: // flag error
            printf("search flag error\n");
            return NULL;
    }
}

rangeSerchRst_t RangeSerchSl(SlList_t* slList,ScoreType s1,ScoreType s2)
{
    rangeSerchRst_t out;
    if(s2<s1)
    {
        out.headNode=NULL;
        return out;
    }
    out.headNode=serchSl(slList,s1,GE);
    if(out.headNode==NULL)
        return out;
    if(out.headNode->score==s2)
    {
        out.tailNode=out.headNode;
        return out;
    }
    if(out.headNode->score > s2)
    {
        out.headNode=NULL;
        return out;
    }
    out.tailNode=serchSl(slList,s2,LE);
    printRangeSerchRst(slList,&out);
    
    return out;
}

void printRangeSerchRst(SlList_t* slList,rangeSerchRst_t* result)
{
    SlNode_t* node=result->headNode;
    printf("range serch results:\n");
    if(node==NULL)
    {
        printf("  none\n");
        return;
    }
    while(node)
    {
        printf("  %d\n",node->score);
        if(node==result->tailNode)
            return;
        node=node->level[0].forward;
    }
}

int32_t rankSerchSl(SlList_t* slList,ScoreType score,int32_t flag)
{
    // flag equal GE means rank of the score
    int32_t levelII;
    int32_t rank=0;
    SlNode_t* node=slList->head;
    SlNode_t* next;
    for(levelII=slList->level-1;levelII>=0;levelII--)
    {
        //printf("level %d\n",levelII);
        next=node->level[levelII].forward;
        if(next==NULL || next->score > score)
            continue;
        if(next->score == score)
            return rank+node->level[levelII].span;
        else if(next->score < score)
        {
            rank+=node->level[levelII].span;
            node=next;
            levelII++;
        }
    }
    switch(flag){
        case 0: // equal
            return -1;
        case 1: // greater than or equal
            return rank+1;
        // case 2: // less than or equal
        //     return node==slList->head?-1:rank;
        default: // flag error
            printf("search flag error\n");
            return -1;
    }
}

void printSl(SlList_t* slList) // score must be int
{
    int ii;
    int32_t levelII;
    int32_t spanII;
    int length=slList->length;
    SlNode_t* x=slList->head;

    printf("-------- skip list --------\n");
    for(levelII=slList->level-1;levelII>=0;levelII--)
    {
        x=slList->head;
        while(x)
        {
            if(x==slList->head)
                printf("[head]");
            else
                printf("->[%4d]",x->score);
            if(x->level[levelII].forward==NULL)
                break;
            for(spanII=1;spanII<x->level[levelII].span;spanII++)
                printf("--------");
            x=x->level[levelII].forward;
        }
        printf("\n");
    }
}

void freeSlList(SlList_t* slList)
{
    SlNode_t* node=slList->head;
    SlNode_t* next;
    while(node)
    {
        next=node->level[0].forward;
        freeSlNode(node);
        node=next;
    }
    free(slList);
}

inline void freeSlNode(SlNode_t* node)
{
    free(node);
}

/* skip list test
int main()
{
    int32_t ii;
    int32_t elem=10;
    SlList_t* sl=createSlList();
    if(sl==NULL) return -1;
    for(ii=0;ii<12;ii++)
    {
        insertNoteSl(sl,ii+10,&elem);
    }
    printSl(sl);
    deletNoteSl(sl,sl->head->level[2].forward);
    printSl(sl);
    deletNoteSl(sl,sl->head->level[0].forward);
    printSl(sl);
    deletNoteSl(sl,sl->head->level[4].forward);
    printSl(sl);
    deletNoteSl(sl,sl->tail);
    printSl(sl);
    deletNoteSl(sl,sl->head->level[1].forward);
    printSl(sl);
    deletNoteSl(sl,sl->head->level[1].forward);
    printSl(sl);
    for(ii=0;ii<5;ii++)
        deletNoteSl(sl,sl->tail);
    printSl(sl);
    deletNoteSl(sl,sl->tail);
    printSl(sl);
    return 0;
}
*/

/*----------------- Algorithm -----------------*/
void findMaxUint64(
    uint64_t* maxVal,uint32_t* index, // output
    uint64_t* list, uint32_t start, uint32_t end)
{
    uint32_t ii;
    *maxVal = list[start];
    *index = start;
    for (ii = start; ii <= end; ii++)
    {
        if (list[ii] > *maxVal)
        {
            *maxVal = list[ii];
            *index = ii;
        }   
    }
}
uint64_t myMeanUint64(uint64_t* list, uint32_t start, uint32_t end)
{
    uint64_t sum=0;
    uint32_t ii;
    for (ii = start; ii <= end; ii++)
    {
        sum += list[ii];
    }
    return sum / (end+1 - start);
}
inline uint32_t myMaxUint32(uint32_t a, uint32_t b)
{
    return a > b ? a : b;
}
inline uint32_t myMinUint32(uint32_t a, uint32_t b)
{
    return a < b ? a : b;
}

inline uint32_t myAbsInt32(int32_t a)
{
    return a > 0 ? a : -a;
}

/*----------------- rand -----------------*/
static uint32_t randSeed;

uint32_t myRand() // 没有考虑多线程情况
{
    uint32_t r;
    r = randSeed = (randSeed * 1103515245 + 12345) & 0x7fffffff;
    return r;
}

void mySrand(uint32_t seed)
{
    randSeed=(seed==0?1:seed);
    myRand();
    myRand();
    myRand();
}


/* queue demo
int main()
{
    int ii, out, tt;
    Queue q;

    if ((q=createQueue(10)) == NULL)
        return -1;
    for (ii = 0; ii < 15; ii++)
    {
        out = inQue(ii, q);
        if (out != 0)
            printf("out %d\n", ii);
    }
    for (ii = 0; ii < 15; ii++)
    {
        out = deQue(&tt, q);
        if (out != 0)
            printf("\tout %d\n", ii);
        else
            printf("data %d\n", tt);
    }
    disposeQue(q);

    return 0;
}
*/

/* list demo
int main()
{
    int ii;

    List L=emptyList(NULL);
    for(ii=0;ii<5;ii++)
        appendNode(L, ii+10);
    printList(L, printInt);
    deleNode(L->next);
    printList(L, printInt);
    
    deleList(L);
    return 0;
}
*/

/* skip list search and rank test
int main()
{
    int32_t ii;
    int32_t elem=10;
    int32_t rank;
    SlNode_t* out;
    SlList_t* sl=createSlList();

    if(sl==NULL) return -1;
    for(ii=0;ii<10;ii++)
    {
        insertNodeSl(sl,ii+10,&elem);
    }
    deletNodeSl(sl,sl->head->level[1].forward);
    printSl(sl);

    out=serchSl(sl,12,GE);
    if(out==NULL)
        printf("no find\n");
    else
        printf("find %d\n",out->score);

    RangeSerchSl(sl,20,20);
    rank=rankSerchSl(sl,3,GE); // GE means rank of the score
    printf("rank %d\n",rank);

    freeSlList(sl);
    return 0;
}
*/